package com.lihui;

import java.util.Arrays;
import java.util.Random;
import java.util.Stack;

/**
 * 功能描述
 * 排序的所有算法
 * @author wileda
 * @date 2022/11/10  20:00
 */
public class Sort {
    /**
     * 插入排序
     * 时间复杂度：O(N^2)
     * 空间复杂度：0(1)
     * 稳定性：稳定
     * @param array
     */
    public  static void insertSort(int[] array){
        for(int i = 1; i < array.length; i++){
            int temp = array[i];
            int j = i - 1;
            while(j >= 0){
                if(array[j] <= temp){
                    break;
                }
                array[j + 1] = array[j];
                j--;
            }
            array[j + 1] = temp;
        }
    }

    // 测试插入排序
    private static void testInsertSort (int [] array) {
        // 记录开始时间
        long begin = System.currentTimeMillis();
        insertSort(array);
        // 记录结束时间
        long end  = System.currentTimeMillis();
        System.out.println("插入排序耗时：" + (end - begin));
    }


    /**
     * 希尔排序
     * 时间复杂度:O(n^1.25)~O(n^1.5)
     * 空间复杂度:O(1)
     * 稳定性：不稳定
     * @param array
     */

    public static void shellSort (int[] array) {
        // 1. 确定增量的大小
        int gap = array.length / 2;
        while (gap > 0) {
            shell(array, gap);
            // gap每次变成原来的1/2
            gap /= 2;
        }
    }

    private static void shell(int[] array, int gap) {
        for (int i = gap; i < array.length; i++) {
            int  j = i - gap;
            int temp = array[i];
            while(j >= 0){
                if(array[j] < temp){
                    break;
                }
                array[j + gap] = array[j];
                j -= gap ;
            }
            array[j + gap] = temp;
        }
    }

    // 测试希尔排序
    private static void testShellSort (int [] array) {
        // 记录开始时间
        long begin = System.currentTimeMillis();
        shellSort(array);
        // 记录结束时间
        long end  = System.currentTimeMillis();
        System.out.println("希尔排序耗时：" + (end - begin));
    }

    /**
     * 直接选择排序
     * 时间复杂度：O(N^2)，与数组是否有序没关系不大
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     * @param array
     */

    public static void selectSort (int[] array) {
        // 1. 从0 下标开始向后遍历
        for (int i = 0; i < array.length; i++) {
            // 2. 记录最小值下标，默认最小值下标是i
            int minIndex = i;
            // 3. j从i + 1 下标开始向后遍历
            for (int j = i + 1; j < array.length; j++) {
                // 4. 如果找到比当前minIndex 还小的值，那么更新minIndex下标到j
                if (array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            // 交换minIndex和i的元素
            swap(array, minIndex, i);
        }
    }


    public static void selectSort2(int[] array){
        int left = 0;
        int right = array.length - 1;
        while(left < right){
            int minIndex = left;
            int maxIndex = left;
            for (int i = left + 1; i <= right; i++) {
                if (array[i] < array[minIndex]) {
                    minIndex = i;
                }
                if (array[i] > array[maxIndex]) {
                    maxIndex = i;
                }
            }
            if(left != minIndex){
                swap(array,left,minIndex);
            }
            if (left == maxIndex){
                maxIndex = minIndex;
            }

            if(right != maxIndex){
                swap(array,right,maxIndex);
            }
            left++;
            right--;
        }
    }


    private static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }


    // 测试直接选择排序
    private static void testSelectSort (int [] array) {
        // 记录开始时间
        long begin = System.currentTimeMillis();
        selectSort(array);
        // 记录结束时间
        long end  = System.currentTimeMillis();
        System.out.println("直接选择排序耗时：" + (end - begin));
    }

    private static void testSelectSort2 (int [] array) {
        // 记录开始时间
        long begin = System.currentTimeMillis();
        selectSort2(array);
        // 记录结束时间
        long end  = System.currentTimeMillis();
        System.out.println("直接选择排序2耗时：" + (end - begin));
    }


    /**
     * 堆排序
     * 时间复杂度:O(N*logN)
     * 空间复杂度:O(1)
     * 稳定性：不稳定
     * @param array
     */
    public static void heapSort(int[] array){
        createHeap(array);
        int end = array.length - 1;
        while(end >= 0){
            swap(array,0,end);
            shiftDown(array,0,end);
            end--;
        }
    }

    private static void createHeap(int[] array) {
        for (int parent = (array.length - 2)/ 2; parent>= 0; parent--){
            shiftDown(array,parent,array.length);
        }
    }

    private static void shiftDown(int[] array, int parent, int length) {
        int child = parent * 2 + 1;
        while(child < length) {
            if (child + 1 < length) {
                if (array[child + 1] > array[child]) {
                    child++;
                }
            }
            if(array[parent] > array[child]){
                break;
            }
            swap(array, parent, child);
            parent = child;
            child = parent * 2 + 1;
        }
    }

    private static void testHeapSort (int [] array) {
        // 记录开始时间
        long begin = System.currentTimeMillis();
        heapSort(array);
        // 记录结束时间
        long end  = System.currentTimeMillis();
        System.out.println("堆排序耗时：" + (end - begin));
    }

    /**
     * 冒泡排序
     * 时间复杂度：O(N^2)
     * 空间复杂度：O(1)
     * 稳定性：稳定
     * @param array
     */
    public static void bubbleSort(int[] array){
        for (int i = 0; i < array.length - 1; i++) {
            for (int j = 0; j < array.length - i - 1; j++) {
                if(array[j] > array[j + 1]){
                    swap(array, j + 1, j );
                }
            }
        }
    }

    private static void testBubbleSort (int [] array) {
        // 记录开始时间
        long begin = System.currentTimeMillis();
        bubbleSort(array);
        // 记录结束时间
        long end  = System.currentTimeMillis();
        System.out.println("冒泡排序耗时：" + (end - begin));
    }

    /**
     * 快速排序
     * 时间复杂度: O(N*logN)
     * 空间复杂度: O(LogN)
     * 稳定性: 不稳定
     * @param array
     */

    public static void quickSort(int[] array){

        quickSortProcess(array,0,array.length - 1);
    }

    private static void quickSortProcess(int[] array, int left, int right) {
        if(left >= right){
            return;
        }
        // =======================三数取中 开始=========
        int middle = middleValue(array,left,right);
        swap(array,left,middle);
        // =======================三数取中 结束=========

        int pivot = partitionHoare(array,left,right);
        quickSortProcess(array,left,pivot - 1);
        quickSortProcess(array,pivot + 1,right);
    }


    // Hoare法找基准
    private static int partitionHoare(int[] array, int left, int right)     {
        int pivotValue = array[left];
        int pivotIndex = left;
        while(left < right){
            while (left < right && pivotValue <= array[right]){
                right--;
            }
            while(left < right && pivotValue >= array[left]){
                left++;
            }
            swap(array,left,right);
        }
        swap(array,left,pivotIndex);
        return left;
    }

    //挖坑法
    private static int partitionHoare2(int[] array, int left, int right) {
        int pivotValue = array[left];
        while(left < right){
            while(left < right && array[right] >= pivotValue){
                right--;
            }
            array[left] = array[right];
            while(left < right && array[left] <= pivotValue){
                left++;
            }
            array[right] = array[left];
        }

        array[left] = pivotValue;
        return left;
    }

    //快慢指针法
    private static int partitionHoare3(int[] array, int left, int right) {
        int prev = left;
        int current = left + 1;
        while(current <= right){
            if(array[current] < array[left]){
                prev++;
                if(array[prev] != array[current]){
                    swap(array,current,prev);
                }
            }
            current++;
        }
        swap(array,prev,left);
        return prev;
    }

    //三数取中法
    public static int middleValue(int[] array,int left, int right){
        int middle = (left + right) / 2;
        if(array[left] < array[right]){
            if(array[middle] > array[right]){
                return right;
            }else if(array[middle] < array[left]){
                return left;
            }
            return middle;
        }else {
            if(array[middle] < array[right]){
                return right;
            }else if(array[left] < array[middle]){
                return left;
            }
            return middle;
        }
    }



    private static void testQuickSort (int [] array) {
        // 记录开始时间
        long begin = System.currentTimeMillis();
        quickSort(array);
        // 记录结束时间
        long end  = System.currentTimeMillis();
        System.out.println("快速排序耗时：" + (end - begin));
    }

    public static void quickSortItr(int[] array){
        //定义一个栈来记录区段的左右下标
        Stack<Integer> stack = new Stack<>();
        //确定下标值
        int left = 0;
        int right = array.length - 1;
        //三数取中
        int mid = middleValue(array,left,right);
        swap(array,left,mid);
        //找基准值
        int pivot = partitionHoare(array,left,right);
        if (left + 1 < pivot){
            stack.push(left);
            stack.push(pivot - 1);
        }
        if(right - 1 > pivot){
            stack.push(pivot + 1);
            stack.push(right);
        }
        while(!stack.isEmpty()){
            right = stack.pop();
            left = stack.pop();
          mid = middleValue(array,left,right);
            swap(array,left,mid);
            //找基准值
           pivot = partitionHoare(array,left,right);
            if (left + 1 < pivot){
                stack.push(left);
                stack.push(pivot - 1);
            }
            if(right - 1 > pivot){
                stack.push(pivot + 1);
                stack.push(right);
            }
        }
    }


    /**
     * 归并排序
     * 时间复杂度: O(N*logN)
     * 空间复杂度：O(N)
     * 稳定性：稳定
     * @param array
     */
    public static void mergeSort(int[] array)   {
        mergeSortProcessor(array,0, array.length - 1);
    }
    private static void mergeSortProcessor(int[] array,int left,int right){
        if(left >= right){
            return;
        }

        int mid = (left + right) / 2;
        mergeSortProcessor(array,left,mid);
        mergeSortProcessor(array,mid + 1,right);

        merge(array, left, mid, right);
    }

    private static void merge(int[] array, int left, int mid, int right) {
        //1.创建一个临时数组，注意数组容量
        int[] temp = new int[right - left + 1];
        // 临时数组下标
        int index= 0;
        //2.确定每个小数组的下标
        int start1 = left;
        int end1 = mid;
        int start2 = mid + 1;
        int end2 = right;
        //3.归并，归并中排序
        while(start1 <= end1 && start2 <= end2){
            if(array[start1] < array[start2]){
                temp[index] = array[start1];
                index++;
                start1++;
            }else {
                temp[index] = array[start2];
                index++;
                start2++;
            }
        }
        //4.把数组的剩余元素添加到临时数组的末尾
        while (start1 <= end1){
            temp[index++] = array[start1++];
        }
        while (start2 <= end2){
            temp[index++] = array[start2++];
        }
        for (int i = 0; i < temp.length; i++) {
            array[i + left] = temp[i];
        }
    }

    public static void mergeSortItr(int[] array){
        int gap = 1;
        while (gap < array.length) {
            for (int i = 0; i < array.length; i += 2 * gap) {
                int left = i;
                int mid = i + gap - 1;
                int right = mid + gap;

                if (mid >= array.length) {
                    mid = array.length - 1;
                }
                if (right >= array.length) {
                    right = array.length - 1;
                }
                merge(array, left, mid, right);
            }
            gap *= 2;
        }
    }


    /**
     * 计数排序
     * @param array
     */
    public static void counterSort(int[] array){
        int minValue = array[0];
        int maxValue = array[0];
        for (int i = 0; i < array.length; i++) {
            if(array[i] < minValue){
                minValue = array[i];
            }
            if(array[i] > maxValue){
                maxValue = array[i];
            }
        }
       int[] countArray = new int[maxValue - minValue + 1];
        //再次遍历数组记录到对应元素的个数
        for (int i = 0; i < array.length; i++) {
            int index = array[i] - minValue;
            countArray[index]++;
        }
        //遍历计数数组
        int index = 0;
        for (int i = 0; i < countArray.length; i++) {
            while (countArray[i] > 0){
               int value = i + minValue;
               array[index] = value;
               countArray[i]--;
               index++;
            }
        }
    }


    public static final int CAPACITY = 1000_0000;
    public static int[] initOrderArray(){
        int[] array = new int[CAPACITY];
        for (int i = 0; i < array.length; i++) {
            array[i] = i;
        }
        return array;
    }

    public static int[] initUnOrderArray(){
        int[] array = new int[CAPACITY];
        Random random = new Random();
        for (int i = 0; i < array.length; i++) {
            array[i] = random.nextInt(CAPACITY);
        }
        return array;
    }


    public static void main(String[] args) {
        System.out.println("============有序数组=================");
//        testInsertSort(initOrderArray());
//        testShellSort(initOrderArray());
//        testSelectSort(initOrderArray());
//        testSelectSort2(initOrderArray());
//          testHeapSort(initOrderArray());
//          testBubbleSort(initOrderArray());
          testQuickSort(initOrderArray());
        System.out.println("============无序数组=================");
        int[] unOrderArray = initUnOrderArray();
//        testInsertSort(Arrays.copyOf(unOrderArray,unOrderArray.length));
//        testShellSort(Arrays.copyOf(unOrderArray,unOrderArray.length));
//        testSelectSort(Arrays.copyOf(unOrderArray,unOrderArray.length));
//        testHeapSort(Arrays.copyOf(unOrderArray,unOrderArray.length));
//        testBubbleSort(Arrays.copyOf(unOrderArray,unOrderArray.length));

        testQuickSort(Arrays.copyOf(unOrderArray,unOrderArray.length));

    }
}
